using System.Collections.Generic;
using System.Linq;
using NUnit.Framework;

namespace ProjectEuler.Core
{
    public class Problem24 : IProjectEulerProblem
    {
        protected IList<string> LexographicPermutations()
        {
            var list = new List<string>();
            string numbers = "0123456789";
            foreach (var c in numbers)
            {
                list.AddRange(LexographicPermutations(c.ToString(), numbers.Replace(c.ToString(), "")));
            }
            return list.OrderBy(x => x).ToList();
        }

        private IEnumerable<string> LexographicPermutations(string prefix, string numbers)
        {
            var list = new List<string>();
            if (numbers == string.Empty)
            {
                list.Add(prefix);
            }
            else
            {
                foreach (var n in numbers)
                {
                    list.AddRange(LexographicPermutations(prefix + n, numbers.Replace(n.ToString(), "")));
                }
            }
            return list;
        }

        // this is "theogeer"s solution from the project euler forums:
        //
        // I started with a string "0123456789" 
        // I know there are 9! permutations of those characters. 
        // Of those, the first 8! begin with a 0 
        // So if the Row number (999999 using a 0 index) minus 8! is < 1 then it is 0, if the row number minus 8! is less than 8!, then it is 2, etc. etc.
        public static string LexographicPermutationsFast(string numbers, int p)
        {
            p--;
            string t = "";
            int length = numbers.Length;

            for (int i = 0; i < length; i++)
            {
                int factor = AlmostFactorial(numbers.Length);

                int cycleNum;
                if (p < factor)
                {
                    cycleNum = 0;
                }
                else
                {
                    if (factor == 1)
                    {
                        cycleNum = p;
                    }
                    else
                    {
                        cycleNum = (p / factor);
                    }
                }

                while (cycleNum >= numbers.Length)
                {
                    cycleNum -= numbers.Length;
                }

                t += numbers.Substring(cycleNum, 1);
                numbers = numbers.Substring(0, cycleNum) + numbers.Substring(cycleNum + 1);
            }
            t += numbers;
            return t;
        }

        public static int AlmostFactorial(int n)
        {
            int factorial = 1;
            for (int i = 1; i < n; i++)
            {
                factorial *= i;
            }
            return factorial;
        }

        public int Number
        {
            get { return 24; }
        }

        public string Description
        {
            get { return "What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?"; }
        }

        public string Answer
        {
            get
            {
                return LexographicPermutationsFast("0123456789", 1000000);
                //return LexographicPermutations()[999999];
            }
        }
    }
}
